package prefixsum;

import java.util.HashSet;
import java.util.Set;

/**
 * 给你一个数组 nums 和一个整数 target 。
 * 请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。
 * <p>
 * 示例 1：
 * 输入：nums = [1,1,1,1,1], target = 2
 * 输出：2
 * 解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。
 * <p>
 * 示例 2：
 * 输入：nums = [-1,3,5,1,4,2,-9], target = 6
 * 输出：2
 * 解释：总共有 3 个子数组和为 6 。
 * ([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。
 * <p>
 * 示例 3：
 * 输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
 * 输出：3
 * <p>
 * 示例 4：
 * 输入：nums = [0,0,0], target = 0
 * 输出：3
 *
 * @author Jisheng Huang
 * @version 20250526
 */
public class MaxNonOverlapping_1546 {
    /**
     * @param nums   the given integer array
     * @param target the given integer target
     * @return the maximum cases that can sum up to the target
     */
    public static int maxNonOverlapping(int[] nums, int target) {
        Set<Integer> set = new HashSet<Integer>() {{
            add(0);
        }};
        int count = 0;
        int sum = 0;

        for (int x : nums) {
            sum += x;

            if (set.contains(sum - target)) {
                set.clear();
                ++count;
            }

            set.add(sum);
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        int target = 2;

        System.out.println(maxNonOverlapping(nums, target));

        nums = new int[]{-1, 3, 5, 1, 4, 2, -9};
        target = 6;

        System.out.println(maxNonOverlapping(nums, target));

        nums = new int[]{-2, 6, 6, 3, 5, 4, 1, 2, 8};
        target = 10;

        System.out.println(maxNonOverlapping(nums, target));
    }
}
